﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._40
{

    /*
     34. Search for a Range

        Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4]. 
         */
    public class Leetcode34
    {
        /// <summary>
        /// 假设数据是升序排列
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int[] SearchRange(int[] nums, int target)
        {
            int iStart = -1, iEnd = -1;
            int minIndex = 0;
            int maxIndex = nums.Length;
            int tempIndex = (maxIndex - minIndex) / 2;

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[tempIndex] < target)
                {
                    minIndex = tempIndex;
                    tempIndex = tempIndex + (maxIndex - minIndex) / 2;
                }
                else if (nums[tempIndex] > target)
                {
                    maxIndex = tempIndex;
                    tempIndex = minIndex + (maxIndex - minIndex) / 2;
                }
                else
                {
                    iStart = tempIndex;
                    break;
                }
            }
            if (iStart < 0)
                return new int[] { -1, -1 };
            iEnd = iStart;
            for (int i = iStart + 1; i < nums.Length; i++)
            {
                if (nums[i] == target)
                    iEnd = i;
                else
                    break;
            }

            for (int i = iStart - 1; i >= 0; i--)
            {
                if (nums[i] == target)
                    iStart = i;
                else
                    break;
            }

            return new int[] { iStart, iEnd };
        }

        public int[] SearchRange1(int[] nums, int target)
        {
            List<int> list = new List<int>(nums);
            int iStart = list.IndexOf(target);
            if (iStart < 0)
                return new int[] { -1, -1 };
            int iEnd = list.LastIndexOf(target);
            return new int[] { iStart, iEnd};
        }
    }
}
